package test;

public class Mpower {

	public static void main(String[] args) {
		System.out.println(mpower(2, 3, 3));
	}
	
	private static int mpower(int b, int n, int m)
	{
		if(n == 0)
		{
			return 1;
		}
		else if(!isOdd(n))
		{
			int m1 = mpower(b, n / 2, m);
			return m1 * m1 % m;
		}
		else
		{
			int m1 = mpower(b, n - 1, m);
			return (m1 * (b % m)) % m;
		}
	}
	
	private static boolean isOdd(int b)
	{
		return (b & 1) == 1;
	}
}
